package org.groupg.practice;

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;

import java.util.*;

public class JGraphTExample {

    public static void main(String[] args) {
        // 创建一个有向图
        Graph<String, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);

        // 添加顶点
        graph.addVertex("a");
        graph.addVertex("b");
        graph.addVertex("c");
        graph.addVertex("e");
        graph.addVertex("f");
        graph.addVertex("g");

        // 添加边
        graph.addEdge("a", "c");
        graph.addEdge("b", "c");
        graph.addEdge("c", "e");
        graph.addEdge("e", "g");
        graph.addEdge("f", "g");

        // 使用 BFS 按层次遍历图
        System.out.println("BFS Traversal starting from 'a':");
        bfsTraversal(graph, "a");

        System.out.println("\nBFS Traversal starting from 'a' and 'b' (simulating by merging results):");
        // 若要从多个起点开始，可以手动合并结果，这里是一个简单模拟
        Set<String> visited = new HashSet<>();
        bfsTraversalFromMultipleSources(graph, List.of("a", "b"), visited);
    }

    private static void bfsTraversal(Graph<String, DefaultEdge> graph, String startVertex) {
        List<List<String>> levels = new ArrayList<>();
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.add(startVertex);
        visited.add(startVertex);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<String> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                String current = queue.poll();
                currentLevel.add(current);

                for (String neighbor : graph.vertexSet().stream().filter(v -> graph.containsEdge(current, v)).toList()) {
                    if (!visited.contains(neighbor)) {
                        queue.add(neighbor);
                        visited.add(neighbor);
                    }
                }
            }

            levels.add(currentLevel);
        }

        // 输出每一层
        for (int i = 0; i < levels.size(); i++) {
            System.out.println("Layer " + i + ": " + levels.get(i).toString());
        }
    }

    private static void bfsTraversalFromMultipleSources(Graph<String, DefaultEdge> graph, List<String> startVertices, Set<String> visited) {
        for (String startVertex : startVertices) {
            // 为每个起点创建一个新的访问集合（避免共享）
            Set<String> singleSourceVisited = new HashSet<>(visited);
            bfsTraversalWithExistingVisited(graph, startVertex, singleSourceVisited);
        }
    }

    private static void bfsTraversalWithExistingVisited(Graph<String, DefaultEdge> graph, String startVertex, Set<String> visited) {
        Queue<String> queue = new LinkedList<>();

        if (!visited.contains(startVertex)) {
            queue.add(startVertex);
            visited.add(startVertex);
        }

        while (!queue.isEmpty()) {
            String current = queue.poll();
            System.out.print(current + " "); // 直接输出访问顺序

            for (String neighbor : graph.vertexSet().stream().filter(v -> graph.containsEdge(current, v)).toList()) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }
}